這篇文章會用 TDD 手刻 myEmptySequence、mySequenceOf、myAsSequence、myGenerateSequence，把 Sequence 的基礎建設搞起來，為後面幾篇的 Lazy filter/map 鋪路

Kotlin ↔ C# 對照表

asSequence() 和 AsEnumerable() 這兩個都是在做「換一組運算子」這件事，但換的理由完全不同

Kotlin 換的是求值策略。Iterable 的 filter、map 是 eager 的，每一步都產生一個中間 List；asSequence() 之後改用 Sequence 的運算子，變成 Lazy，中間的 List 就不見了。這是執行時行為真的變了

C# 的官方文件講得很直白，AsEnumerable()「has no effect other than to change the compile-time type」，只改編譯期型別，執行時什麼事都沒發生。它的用途是當一個型別除了 IEnumerable<T> 之外還有自己一套查詢方法時，把那些方法藏起來、改用 System.Linq.Enumerable 的標準運算子。最典型的是 IQueryable，Where 本來會被翻成 SQL 丟給資料庫執行，中間插一個 AsEnumerable() 就改成把資料拉回記憶體，用 LINQ to Objects 跑

所以兩邊都是切換運算子，只是 Kotlin 切的是 eager 或 Lazy，C# 兩邊本來就都是 Lazy，切的是「在哪裡執行」

generateSequence 這一列則是另一種情況。它是一個現成的函式，給起始值和「怎麼算下一個」就有序列可以用，在 C# 沒有對應的函式，同樣的事要自己寫一個回傳 IEnumerable<T> 的方法，在裡面用 yield return 把值一個一個吐出來

// C# 沒有 generateSequence，得自己寫一個
static IEnumerable<int> Generate(int seed, Func<int, int> next) {
    var current = seed;
    while (true) {
        yield return current;
        current = next(current);
    }
}

另外這個 C# 版是無限的，Kotlin 那邊用 nextFunction 回傳 null 當結束訊號，C# 要停的話得自己在迴圈裡加條件

yield 看起來像魔法，其實是 coroutine 機制的應用

C# 的 yield return 在編譯期會被改寫成一個 state machine class，把每次 yield 的位置變成 case label，呼叫 MoveNext() 從上次的位置繼續執行。Kotlin 的 sequence { yield() } 用 suspend 函式 + coroutine builder 實作，概念類似但底層是 continuation passing style，把「做完事之後要怎樣」打包成一個 continuation 物件，讓 yield 能保留執行狀態

兩個機制都不是真的「暫停執行緒」，而是把執行流程拆成多段：執行到下一個 yield 點就回去，下次從那個點繼續。Sequence 因此能表達無限序列，例如 generateSequence(0) { it + 1 }；它不會先把所有元素物化，但 Iterator、continuation 與 Lambda 捕捉的狀態仍會占用記憶體

這篇我們不直接用 coroutine builder，而是用更基本的 Sequence { } 工廠函式

這裡先講清楚一件事。Sequence 介面本身只有一個 iterator() 方法，沒有實作細節可挖。前面手刻 Iterable 的操作時也是一樣的做法：從 day 03 的 myFilter 開始，我們寫的都是掛在 stdlib Iterable<T> 上的 extension function，從來沒有自己宣告過集合介面。自己再宣告一個 MySequence 介面只是把同樣的單方法抄一遍，沒什麼學習價值。同理 Sequence { } 這個工廠函式也只是把 Lambda 包成 Sequence 物件，等同於 object : Sequence<T> { override fun iterator() = ... }。所以這篇沿用 stdlib 的 Sequence 介面和 Sequence { }，把力氣花在後面幾個真正有邏輯的工廠函式上

TDD 實作 myEmptySequence

先從空的開始，因為等一下的 mySequenceOf 在沒有元素的時候會直接拿它來用

Red：先寫測試

@Test
fun `empty sequence has no elements`() {
    val seq = myEmptySequence<Int>()
    assertEquals(emptyList<Int>(), seq.toList())
}

@Test
fun `empty sequence iterator next throws`() {
    val seq = myEmptySequence<Int>()
    assertThrows(NoSuchElementException::class.java) {
        seq.iterator().next()
    }
}

Green：最小實作

fun <T> myEmptySequence(): Sequence<T> {
    return Sequence { object : Iterator<T> {
        override fun hasNext(): Boolean = false
        override fun next(): T = throw NoSuchElementException("Empty sequence.")
    }}
}

Sequence { } 是 stdlib 提供的工廠函式，接收一個 () -> Iterator<T> 的 Lambda。每次有人呼叫 iterator()，這個 Lambda 就會被執行一次，產生一個新的 Iterator

這裡回傳的是一個永遠 hasNext() = false 的 Iterator。object : Iterator<T> 是匿名物件，day 02 講 Lambda 的時候提過這個語法

Refactor：往 stdlib 的寫法靠近

邏輯上已經沒得改，stdlib 唯一多做的是把空 Sequence 做成 singleton 共用，這個差異留到「與 stdlib 原始碼比較」段落再看

TDD 實作 mySequenceOf

Red：先寫測試

@Test
fun `sequenceOf with elements`() {
    val seq = mySequenceOf(1, 2, 3)
    assertEquals(listOf(1, 2, 3), seq.toList())
}

@Test
fun `sequenceOf no elements returns empty`() {
    val seq = mySequenceOf<Int>()
    assertEquals(emptyList<Int>(), seq.toList())
}

@Test
fun `sequenceOf can be iterated multiple times`() {
    val seq = mySequenceOf(1, 2, 3)
    assertEquals(listOf(1, 2, 3), seq.toList())
    assertEquals(listOf(1, 2, 3), seq.toList())
}

最後一個測試驗證 mySequenceOf 的合約：每次呼叫 iterator() 都會從陣列拿到一個全新的 Iterator，所以同一個 Sequence 可以走訪很多次。但這是 mySequenceOf 自己的性質，不是所有 Sequence 都這樣，有些只能走訪一次，後面比較 stdlib 原始碼時會看到

Green：最小實作

fun <T> mySequenceOf(vararg elements: T): Sequence<T> {
    if (elements.isEmpty()) {
        return myEmptySequence()
    }
    return Sequence { elements.iterator() }
}

沒有元素的時候直接回傳剛才寫好的 myEmptySequence()，有元素就用 Sequence { } 把 Array 的 iterator 包起來

vararg 讓呼叫方可以寫 mySequenceOf(1, 2, 3)，底層收到的是一個 Array。Array 有 iterator() 方法，直接拿來用

Refactor：往 stdlib 的寫法靠近

這個實作已包含 sequenceOf 的兩條路徑：空陣列回傳 empty，有元素就包裝 iterator。後面的原始碼比較會確認剩餘差異

TDD 實作 myAsSequence

Red：先寫測試

@Test
fun `list to sequence`() {
    val list = listOf(1, 2, 3)
    val seq = list.myAsSequence()
    assertEquals(listOf(1, 2, 3), seq.toList())
}

@Test
fun `set to sequence`() {
    val set = setOf("a", "b", "c")
    val seq = set.myAsSequence()
    assertEquals(listOf("a", "b", "c"), seq.toList())
}

@Test
fun `empty iterable to sequence`() {
    val seq = emptyList<Int>().myAsSequence()
    assertEquals(emptyList<Int>(), seq.toList())
}

Green：最小實作

fun <T> Iterable<T>.myAsSequence(): Sequence<T> {
    return Sequence { this.iterator() }
}

每次呼叫 iterator() 時，都從原本的 Iterable 取得新的 Iterator。因此，只要底層 Iterable 本身支援重複走訪，這個 Sequence 也可以重複走訪

Refactor：往 stdlib 的寫法靠近

一行的實作，跟 stdlib 的 asSequence 就是同一個寫法，這輪沒有東西可以重構

TDD 實作 myGenerateSequence

generateSequence 是 Kotlin 裡產生無限序列的方式。給一個起始值和一個計算下一個值的函式

Red：先寫測試

@Test
fun `generate natural numbers`() {
    val seq = myGenerateSequence(0) { it + 1 }
    val result = seq.take(5).toList()
    assertEquals(listOf(0, 1, 2, 3, 4), result)
}

@Test
fun `generate with seed and next`() {
    val seq = myGenerateSequence(1) { it * 2 }
    val result = seq.take(5).toList()
    assertEquals(listOf(1, 2, 4, 8, 16), result)
}

@Test
fun `generate terminates when null returned`() {
    val seq = myGenerateSequence(1) { if (it < 4) it + 1 else null }
    assertEquals(listOf(1, 2, 3, 4), seq.toList())
}

@Test
fun `generate with null seed returns empty`() {
    val seq = myGenerateSequence<Int>(null) { it + 1 }
    assertEquals(emptyList<Int>(), seq.toList())
}

@Test
fun `generate from supplier without seed`() {
    var count = 0
    val seq = myGenerateSequence { if (count < 3) ++count else null }
    assertEquals(listOf(1, 2, 3), seq.toList())
}

@Test
fun `generate fibonacci`() {
    val fibs = myGenerateSequence(Pair(0, 1)) { Pair(it.second, it.first + it.second) }
        .map { it.first }
        .take(8)
        .toList()
    assertEquals(listOf(0, 1, 1, 2, 3, 5, 8, 13), fibs)
}

@Test
fun `take does not calculate one extra value`() {
    var calls = 0
    val result = myGenerateSequence(1) {
        calls++
        it + 1
    }.take(5).toList()

    assertEquals(listOf(1, 2, 3, 4, 5), result)
    assertEquals(4, calls)
}

先看最單純的 myGenerateSequence(0) { it + 1 }。seed 是 0，它本身就是序列的第一個值，不用經過任何計算；從第二個值開始，每一圈都拿上一圈吐出來的值丟進 { it + 1 }，算出下一個

• 第 1 個值：直接用 seed，得到 0
• 第 2 個值：拿上一個值 0 呼叫 { it + 1 }，得到 1
• 第 3 個值：拿 1 算出 2
• 第 4、5 個值同理，得到 3 和 4

規則就是「拿上一個值算下一個」，所以換個算法 myGenerateSequence(1) { it * 2 } 就變成 1, 2, 4, 8, 16, ...

這兩個序列理論上都是無限長的，但因為 Sequence 是 Lazy 的，搭配 take(5) 就只會算到第 5 個為止。而且 seed 不用算，nextFunction 只被呼叫四次，這正是最後一個測試在驗的事

Fibonacci 的測試比較有意思：用 Pair 追蹤前兩個數字，搭配 map 取出第一個，一行就寫出費波那契數列

當 nextFunction 回傳 null，序列就結束。所以 { if (it < 4) it + 1 else null } 會在 4 的時候停下來

null 在這裡有兩個位置，意思不一樣。nextFunction 回傳 null 是「後面沒有了」，seed 傳 null 則是「一開始就沒有」，拿到的會是一個空序列

seed 這個參數沒有預設值，不能省略不寫，要嘛給一個值、要嘛明確傳 null。會特別處理 null 是因為實務上 seed 常常來自 list.firstOrNull() 這種本來就可能沒有值的地方，呼叫端可以直接把結果丟進來，不用自己先寫一個 if 擋掉

如果連 seed 這個參數都不想寫，那要找的是另一個只收 supplier 的版本，也就是 generate from supplier without seed 這個測試。它沒有起始值，每一個值都直接問 supplier 要，supplier 回傳 null 就結束。這個版本的實作放在 Green 段落後半

Green：最小實作

fun <T : Any> myGenerateSequence(seed: T?, nextFunction: (T) -> T?): Sequence<T> {
    if (seed == null) {
        return myEmptySequence()
    }
    return Sequence {
        object : Iterator<T> {
            var nextValue: T? = seed
            var nextState = 1 // -1: 下一個還沒算，0: 沒有下一個了，1: 下一個已經算好

            private fun calculateNext() {
                nextValue = nextFunction(nextValue!!)
                nextState = if (nextValue == null) 0 else 1
            }

            override fun hasNext(): Boolean {
                if (nextState == -1) {
                    calculateNext()
                }
                return nextState == 1
            }

            override fun next(): T {
                if (!hasNext()) {
                    throw NoSuchElementException()
                }
                val value = nextValue!!
                nextState = -1
                return value
            }
        }
    }
}

泛型約束 T : Any 很重要。因為 null 被用來當作「序列結束」的訊號，所以 T 本身不能是 nullable 的

函式第一行就把 seed 是 null 的情況擋掉，直接回傳前面寫好的 myEmptySequence()。先做空序列的好處在這裡就看到了，不用在這邊再刻一個「什麼都沒有」的 Iterator

nextState 有三種狀態，要注意它們描述的都是「下一個值」的處境，跟整個序列算到哪裡無關。nextValue 任何時候都只放一個值，不是一路累積的緩衝區

• 下一個還沒算（-1）：nextValue 裡是已經交出去的舊值，還沒去問 nextFunction
• 下一個已經算好（1）：nextValue 裡就是下次要交出去的值
• 沒有下一個了（0）：nextFunction 回傳了 null，序列到此為止

沒有「全部算完」這種狀態。無限序列本來就不會有算完的那一刻，就算是有限的序列，也是走到 null 才知道結束，不會事先知道總共有幾個

next() 回傳目前值後就把狀態標成「下一個還沒算」；等下一次呼叫 hasNext() 或 next()，calculateNext() 才真的執行 nextFunction

拿 myGenerateSequence(0) { it + 1 } 搭配 take(2) 走一遍就很清楚。物件剛建好的時候 nextValue 是 seed 0、狀態是「下一個已經算好」，因為 seed 不用算就是第一個要交出去的值

take(2) 拿滿兩個就停了，不會再呼叫 hasNext()，所以第三個值 2 從頭到尾都沒被算出來。這就是「不多算一筆」的意思：每個值都拖到有人真的來要的那一刻才算

接著是 generate from supplier without seed 那個測試要的版本，只接受 supplier

fun <T : Any> myGenerateSequence(nextFunction: () -> T?): Sequence<T> {
    return Sequence {
        object : Iterator<T> {
            var nextValue: T? = null
            var nextState = -1 // -1: 下一個還沒算，0: 沒有下一個了，1: 下一個已經算好

            private fun calculateNext() {
                nextValue = nextFunction()
                nextState = if (nextValue == null) 0 else 1
            }

            override fun hasNext(): Boolean {
                if (nextState == -1) {
                    calculateNext()
                }
                return nextState == 1
            }

            override fun next(): T {
                if (!hasNext()) {
                    throw NoSuchElementException()
                }
                val value = nextValue!!
                nextState = -1
                return value
            }
        }
    }
}

這個版本沒有 seed，所以 nextState 從「下一個還沒算」開始，而不是有 seed 版的「下一個已經算好」。第一次呼叫 hasNext() 或 next() 時才執行 nextFunction()，之後每取出一筆就回到還沒算的狀態；supplier 回傳 null 時結束

回頭看那個測試就清楚了，count 從 0 開始，每被問一次就 ++count 回傳，數到 3 之後回傳 null，序列跟著結束，最後拿到 1, 2, 3。值是從哪來的完全由 supplier 自己決定，跟前一個值無關，所以讀檔案、收網路封包這種來源也套得進來

Refactor：往 stdlib 的寫法靠近

把兩個版本並排看，hasNext()、next()、calculateNext() 幾乎一模一樣，只差兩件事：起始狀態是「已經算好」還是「還沒算」，以及第一個值從哪裡來

既然這麼像，可不可以讓其中一個直接呼叫另一個就好？兩個方向都不行，而且卡住的地方不一樣

supplier 版不能呼叫 seed 版。要生出 seed 就得先把 supplier 執行一次，但那會在建構的當下就算出第一個值，還沒有人走訪就先算了，Lazy 破功

seed 版也不能呼叫 supplier 版。supplier 不收參數，拿不到「上一個值」，只能把它存在 Sequence { } 外面。狀態一旦跑到 Lambda 外面就變成每個 Iterator 共用，本來每次 iterator() 都能重新走一遍的 seed 版，會退化成只能走訪一次。兩個版本的走訪契約不一樣，硬併會弄壞其中一個

真正的解法是把「第一個值怎麼來」也變成一個函式參數，抽一份共用的實作出來

private class MyGeneratorSequence<T : Any>(
    private val getInitialValue: () -> T?,
    private val getNextValue: (T) -> T?
) : Sequence<T> {
    override fun iterator(): Iterator<T> = object : Iterator<T> {
        var nextValue: T? = null
        var nextState = -2 // -2: 第一個值還沒算，-1: 下一個還沒算，0: 沒有下一個了，1: 已經算好

        private fun calculateNext() {
            nextValue = if (nextState == -2) getInitialValue() else getNextValue(nextValue!!)
            nextState = if (nextValue == null) 0 else 1
        }

        override fun hasNext(): Boolean {
            if (nextState < 0) {
                calculateNext()
            }
            return nextState == 1
        }

        override fun next(): T {
            if (!hasNext()) {
                throw NoSuchElementException()
            }
            val value = nextValue!!
            nextState = -1
            return value
        }
    }
}

這裡改用 private class 而不是 Sequence { }，是為了跟 stdlib 的 GeneratorSequence 對照，反正它不對外公開，兩個工廠函式共用就好

多出來的 -2 是整個重構的關鍵。原本 seed 版在建立 Iterator 的當下就把 seed 塞進 nextValue，現在改成「連第一個值都還沒算」，等有人真的來要才呼叫 getInitialValue()。兩個版本因此走同一套流程，差異全部收進那兩個函式參數裡

hasNext() 的判斷也從 nextState == -1 放寬成 nextState < 0，一次涵蓋 -2 和 -1，兩個都是「還沒算」，只是要問的對象不同

兩個公開函式就只剩薄薄一層

fun <T : Any> myGenerateSequence(seed: T?, nextFunction: (T) -> T?): Sequence<T> {
    if (seed == null) {
        return myEmptySequence()
    }
    return MyGeneratorSequence({ seed }, nextFunction)
}

fun <T : Any> myGenerateSequence(nextFunction: () -> T?): Sequence<T> {
    return MyGeneratorSequence(nextFunction, { nextFunction() })
}

seed 版傳的 { seed } 是純函式，每次 iterator() 都回傳同一個起始值，所以重複走訪還是好的。supplier 版兩個參數塞的是同一個 nextFunction，getNextValue 直接把上一個值丟掉不用，因為對 supplier 來說下一個值本來就跟前一個無關

前面才說不能互相呼叫，這裡 supplier 版看起來卻像把同一個函式傳兩次。差別在於這次沒有人在外面存狀態，狀態全部留在 iterator() 裡面，兩個版本才共用得起來。supplier 版依然只能走訪一次，但那是 supplier 自己帶狀態造成的，跟這份實作無關

行為沒變只是重複的部分不見了，這也就是 stdlib 的寫法，剩下的差異只有一個 constrainOnce()

sequence { } 建構器

Kotlin 還有另一種建立 Sequence 的方式：sequence { } 建構器搭配 yield

val fibonacci = sequence {
    var a = 0
    var b = 1
    while (true) {
        yield(a)
        val next = a + b
        a = b
        b = next
    }
}

fibonacci.take(8).toList()  // [0, 1, 1, 2, 3, 5, 8, 13]

yield(a) 會暫停這個函式，把 a 吐出去給呼叫方。等呼叫方要下一個值的時候，函式從暫停的地方繼續跑

這背後是 Kotlin coroutine 的機制。sequence { } 的 Lambda 被標記為 suspend，yield 是一個 suspend 函式。suspend 函式可以暫停和恢復，不需要真的開一個執行緒

除了 yield，建構器裡還有一個 yieldAll。yield 一次吐一個值，yieldAll 一次把整個 Iterable、Iterator 或另一個 Sequence 的元素全部吐出去

val seq = sequence {
    yield(0)              // 吐一個值
    yieldAll(1..3)        // 吐 1, 2, 3
    yieldAll(listOf(4, 5))  // 吐 4, 5
}

seq.toList()  // [0, 1, 2, 3, 4, 5]

yieldAll 接 Sequence 的時候一樣保持 Lazy，傳一個無限序列進去也不會卡住，要幾個才算幾個。它對應的是 C# 在 yield return 之外用迴圈逐一 yield return 集合元素的寫法

C# 的 yield return 也用相近方式逐次產出值

// C# 版
IEnumerable<int> Fibonacci() {
    int a = 0, b = 1;
    while (true) {
        yield return a;
        (a, b) = (b, a + b);
    }
}

我們不會手刻 sequence { } 建構器，因為它需要 coroutine 的底層支援，超出這個系列的範圍。但理解它的行為就夠了：yield 暫停、next() 恢復，一次產出一個值

與 stdlib 原始碼比較

原始碼位置：kotlin.sequences 的 Sequences.kt

stdlib 的 sequenceOf 跟我們一樣簡單

public fun <T> sequenceOf(vararg elements: T): Sequence<T> {
    return if (elements.isEmpty()) emptySequence() else elements.asSequence()
}

generateSequence 底層使用的 GeneratorSequence，就是我們在 Refactor 寫的那一份，收 getInitialValue 和 getNextValue 兩個函式，用 -2 把第一個值也延後掉。stdlib 那邊的註解寫成 // -2 for initial unknown, -1 for next unknown, 0 for done, 1 for continue，四個狀態的意思完全一樣

結構做成一樣了，但有個行為差異要講清楚

stdlib 的無 seed 版本結尾多了一個 .constrainOnce()

public fun <T : Any> generateSequence(nextFunction: () -> T?): Sequence<T> {
    return GeneratorSequence(nextFunction, { nextFunction() }).constrainOnce()
}

兩個參數的傳法跟我們重構後一模一樣，差別只在結尾這一個呼叫

重點是差別在第二次，stdlib 版會丟 IllegalStateException: This sequence can be consumed only once.，我們手刻的版本則是靜默回傳空 list，因為 supplier 的狀態已經被第一次走訪耗掉了，直接回傳空值比拋例外難除錯，constrainOnce() 存在的理由就是把這種錯誤提早爆出來

前面說有些 Sequence 只能走訪一次，靠的就是 constrainOnce() 這個機制，Iterator<T>.asSequence() 同樣用了它

stdlib 的 emptySequence() 回傳一個 singleton 物件 EmptySequence，避免每次呼叫都建新物件。我們的實作每次呼叫都會建一個新的匿名物件，功能上沒差，只是少了這層共用

小結

Sequence 介面只有一個 iterator() 方法。常見建立方式包括：sequenceOf 從元素建立、asSequence 從 Iterable 轉換、generateSequence 從計算邏輯產生；sequence { } 建構器則用 coroutine 的 yield 暫停與恢復

下一篇在這個基礎上實作 Sequence 版的 filter 和 map，看看 Lazy 操作怎麼用包裝 Sequence 的方式延遲執行

參考資料

• Kotlin 官方文件：Sequences
• Kotlin API：Sequence
• Kotlin API：sequenceOf
• Kotlin API：emptySequence
• Kotlin API：asSequence
• Kotlin API：generateSequence
• Kotlin API：sequence
• Kotlin API：yield
• Kotlin API：yieldAll
• Kotlin stdlib 原始碼：Sequences.kt
• Java API：Iterator
• .NET API：Enumerable.Empty
• .NET API：Enumerable.AsEnumerable
• .NET API：IEnumerable 介面
• C# 官方文件：yield 陳述式

同步刊登於 Blog

圖片來源：AI 產生